package com.yulan.Tree;

/**
 * 437. 路径总和 III
 */
public class LeetCode_437 {

    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
         int result = dfs(root,sum);
         int a = pathSum(root.left,sum);
         int b = pathSum(root.right,sum);
         return a + b + result;
    }

    public int dfs(TreeNode root , int curSum){
        if(root==null){
            return 0;
        }
        curSum -= root.val;
        int result = curSum == 0 ? 1 : 0;
        return result + dfs(root.left,curSum) + dfs(root.right,curSum);
    }
}
